package com.leecode.xiehf.page_02;

import com.leecode.Printer;

import java.util.Stack;

/**
 * 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
 * <p>
 * https://leetcode-cn.com/problems/maximal-rectangle/
 */
public class Solution_0085 extends Printer {

    public static void main(String[] args) {
        Solution_0085 solution = new Solution_0085();
        char[][] num1 = new char[][]{
                {'1', '0', '1', '0', '0'},
                {'1', '0', '1', '1', '1'},
                {'1', '1', '1', '1', '1'},
                {'1', '0', '0', '1', '0'}
//                {'0', '1'},
//                {'0', '1'}
        };
        int s = solution.maximalRectangle(num1);
        print(s);
    }

    public int maximalRectangle(char[][] matrix) {
        int height = matrix.length;
        if (height == 0) {
            return 0;
        }
        int width = matrix[0].length;
        int res = 0;
        int[] heights = new int[width];
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                if (matrix[i][j] == '1') {
                    heights[j] += 1;
                } else {
                    heights[j] = 0;
                }
            }
            res = Math.max(res, largestRectangleArea(heights));
        }
        return res;
    }

    public int largestRectangleArea(int[] heights) {
        int res = 0;
        // 穷举法
        int length = heights.length;
        int[] newHeights = new int[length+2];
        newHeights[0]=0;
        newHeights[length+1]=0;
        for (int i = 1; i < length+1; i++) {
            newHeights[i]=heights[i-1];
        }
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < length+2; i++) {
            while (!stack.isEmpty() && newHeights[i]<newHeights[stack.peek()]){
                int cur  = stack.pop();
                int height = newHeights[cur];
                int left = stack.peek();
                int width = i - left - 1;
                res = Math.max(width * height, res);
            }
            stack.push(i);
        }
        return res;
    }
}
